package com.future.interview;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 面试题 08.11. 硬币
 * 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
 *
 * @author weiruibai.vendor
 * Date: 2023/1/17 11:20
 */
public class Solution_0811 {

    private static Solution_0811 instance = new Solution_0811();

    public static void main(String[] args) {
        int n = 10;
        n = 900750;
        //System.out.println(instance.waysToChange(n));
        System.out.println(instance.waysToChange_dp3(n));
        System.out.println(instance.waysToChange_dp2(n));
    }

    /**
     * 超时
     *
     * @param n
     * @return
     */
    public int waysToChange(int n) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(5);
        list.add(10);
        list.add(25);
        return calcWays(list, 0, n);
    }

    private int calcWays(List<Integer> list, int i, int rest) {
        if (i == list.size()) {
            return rest == 0 ? 1 : 0;
        }
        int ans = 0;
        int val = list.get(i);
        for (int zhang = 0; zhang * val <= rest; zhang++) {
            ans += calcWays(list, i + 1, rest - val * zhang);
        }
        return ans;
    }


    /**
     * @param n
     * @return
     */
    public int waysToChange_dp(int n) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(5);
        list.add(10);
        list.add(25);
        Integer[][] dp = new Integer[5][n + 1];
        return calcWays_dp(list, 0, n, dp);
    }

    private int calcWays_dp(List<Integer> list, int i, int rest, Integer[][] dp) {
        if (i == list.size()) {
            return rest == 0 ? 1 : 0;
        }
        if (dp[i][rest] != null) {
            return dp[i][rest];
        }
        int ans = 0;
        int val = list.get(i);
        for (int j = 0; j * val <= rest; j++) {
            ans += calcWays_dp(list, i + 1, rest - val * j, dp);
        }
        dp[i][rest] = ans;
        return ans;
    }

    /**
     * 超时
     *
     * @param n
     * @return
     */
    public int waysToChange_dp2(int n) {
        int[] arr = new int[]{1, 5, 10, 25};
        if (n < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][n + 1];
        dp[N][0] = 1;
        for (int i = N - 1; i >= 0; i--) {
            for (int rest = 0; rest <= n; rest++) {
                int ans = 0;
                int val = arr[i];
                for (int zhang = 0; zhang * val <= rest; zhang++) {
                    //ans += calcWays_dp(list, i + 1, rest - val * zhang, dp);
                    /**
                     * dp[i][rest] =
                     * +dp[i+1][rest-val*0]
                     * +dp[i+1][rest-val*1]
                     * +dp[i+1][rest-val*2]
                     * ...
                     */
                    ans += dp[i + 1][rest - val * zhang];
                }
                dp[i][rest] = ans;
            }
        }
        return dp[0][n];
    }


    /**
     * 超时
     *
     * @param n
     * @return
     */
    public static int waysToChange_dp3(int n) {
        int[] arr = new int[]{1, 5, 10, 25};
        if (n < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][n + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= n; rest++) {
                int ways = dp[index + 1][rest];
                for (int zhang = 1; zhang * arr[index] <= rest; zhang++) {
                    ways += dp[index + 1][rest - (zhang * arr[index])];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][n];
    }

    /**
     * OK
     * 参考Solution_0811.png
     *
     * @param n
     * @return
     */
    public static int waysToChange_dp4(int n) {
        int[] arr = new int[]{1, 5, 10, 25};
        if (n < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][n + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= n; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest - arr[index] >= 0) {
                    dp[index][rest] += (dp[index][rest - arr[index]]) % 1000000007;
                }
            }
        }
        return dp[0][n] % (1000000007);
    }
}
